package graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 使用邻接表来表示图
 *
 * 编辑：
 *  序号为u和v的两个点之间插入边
 *  删除边
 *
 * 方法：
 *  获取图的顶点数
 *  获取边的条数
 *  获取图的类型
 *  获取某个顶点的边
 *  获取入度、出度、度
 *  判断一个无向图是否为一棵树
 *
 * 遍历：
 *  深度优先遍历图
 *  广度优先遍历图
 */
public class GraphIITest {

    public static final int UNDIRECTED = 0;
    public static final int DIRECTED = 1;

    int type;    //图的类型
    GraphNode[] lists;    //用以存储所有的链表结构

    void addEdge(int u, int v) {
        lists[u].neighbors.add(new GraphNode(v));
        if (type == UNDIRECTED) {
            lists[v].neighbors.add(new GraphNode(u));
        }
    }

    // 删除边
    void deleteEdge(int u, int v) {
        lists[u].neighbors.remove(Integer.valueOf(v));
        if (type == UNDIRECTED) {
            lists[v].neighbors.remove(Integer.valueOf(u));
        }
    }

}

// val表示值，neighbors表示相连的定点下标
class GraphNode {
    public int val;

    public List<GraphNode> neighbors;

    public GraphNode() {
        val = 0;
        neighbors = new ArrayList<>();
    }

    public GraphNode(int val) {
        this.val = val;
        neighbors = new ArrayList<>();
    }

    public GraphNode(int val, ArrayList<GraphNode> neighbors) {
        this.val = val;
        this.neighbors = neighbors;
    }
}
